package com.gzsxy.Test;

/**
 * 希尔排序
 */
public class Test2 {

    public static void saymsg(int[] src) {
        for (int i = 0; i < src.length; i++) {
            System.out.print(src[i]);
            System.out.print("  ");
        }
        System.out.println();
    }

    public static void shellSort(int[] src) {
        double d1 = src.length;
        int temp = 0;
        int index = 1;
        while (true) {
            //返回大于等于参数x的最小整数
            d1 = Math.ceil(d1 / 2);
            int d = (int) d1;
            for (int x = 0; x < d; x++) {
                for (int i = x + d; i < src.length; i += d) {
                    int j = i - d;
                    temp = src[i];
                    for (; j >= 0 && temp < src[j]; j -= d) {
                        src[j + d] = src[j];
                    }
                    src[j + d] = temp;
                }
                System.out.println("第" + (index++) + "次排序：");
                saymsg(src);
            }
            if (d == 1) {
                break;
            }
        }
        saymsg(src);
    }


//    public static void main(String[] args) {
//        int[] src = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
//        System.out.println("原始数组排序：");
////        saymsg(src);
////        shellSort(src);
//        shell(src);
//    }


    public static void shell(int[] src) {

        double d1 = src.length;
        int temp = 0;
        int index = 0;

        while (true) {
            //返回大于等于参数x的最小整数
            d1 = Math.ceil(d1 / 2);
            //得到数组的增量
            int d = (int) d1;
            //循环每组元素
            for (int x = 0; x < d; x++) {
                //在增量相同的组内进行直接插入排序
                for (int i = x + d; i < src.length; i += d) {
                    int j = i - d;
                    temp = src[i];
                    for (; j >= 0 && temp < src[j]; j -= d) {
                        src[j + d] = src[j];
                    }
                    src[j + d] = temp;
                }
                System.out.print("第" + index++ + "循环后的数组为");
                say(src);
            }
            if (d == 1) {
                break;
            }

        }
    }

    public static void say(int[] src) {
        for (int i = 0; i < src.length; i++) {
            System.out.print(src[i]);
            System.out.print(" ");
        }
        System.out.println();
    }


    public static void xier(int[] src) {

        int index = 0;
        double gap = src.length;
        while (true) {
            gap = Math.ceil(gap / 2);
            int d1 = (int) gap;
            for (int x = 0; x < d1; x++) {
                for (int i = x + d1; i < src.length; i = i + d1) {
                    int j = i - d1;
                    //一定要给src[i]赋值，i值在循环之外，必须先给赋值
                    int temp = src[i];
                    for (; j >= 0 && temp < src[j]; j = j - d1) {
                        src[j + d1] = src[j];
                    }
                    //temp一定要为src[i]
                    src[j + d1] = temp;
                }
                System.out.println("第" + index++ + "次循环");
                say(src);
            }
            if (d1 == 1) {
                break;
            }

        }
    }


    public static void main(String[] args) {
        int[] src = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        System.out.println("原始数组排序：");
//        saymsg(src);
//        shellSort(src);
        xier(src);
    }


}
